Skip to content

const parent = (i - 1) 1; ​

本节目标:理解“const parent = (i - 1) 1;”的核心思路,并能把它用于实际开发或面试表达。 是在 数组实现的二叉最小堆 中,根据子节点下标 i 计算其父节点下标。

细节说明
二叉堆数组映射0-基索引时:
• 左子 = 2 * i + 1
• 右子 = 2 * i + 2
• 父 = ⌊(i – 1) / 2⌋
>> 1JavaScript 的有符号右移:
把数字按二进制整体右移 1 位,相当于对正整数做 ⌊x / 2⌋(向下取整的除 2)。
i – 1先减 1 再除 2,就得 ⌊(i – 1)/2⌋ —— 正是父节点下标。
为何不用 / 2位移运算比浮点除法更快;>> 会直接给出整数结果,无需 Math.floor()。

举例:

  • 节点索引 i = 5
    • (i - 1) >> 1 = (4) >> 1 = 2 → 父节点索引 2
  • i = 1 → (0) >> 1 = 0 → 父就是根节点。

本站总访问 — 次